盒子
盒子

hiho 1284 - 机会渺茫

2017.04.25 呼呼呼山  热度 ℃

Time Limit:5000ms
Case Time Limit:1000ms
Memory Limit:256MB

Description
小Hi最近在追求一名学数学的女生小Z。小Z其实是想拒绝他的，但是找不到好的说辞，于是提出了这样的要求：对于给定的两个正整数N和M，小Hi随机选取一个N的约数N’，小Z随机选取一个M的约数M’，如果N’和M’相等，她就答应小Hi。
小Z让小Hi去编写这个随机程序，到时候她review过没有问题了就可以抽签了。但是小Hi写着写着，却越来越觉得机会渺茫。那么问题来了，小Hi能够追到小Z的几率是多少呢？
Input
每个输入文件仅包含单组测试数据。
每组测试数据的第一行为两个正整数N和M，意义如前文所述。
对于40%的数据，满足1\<=N,M\<=106
对于100%的数据，满足1\<=N,M\<=1012
Output
对于每组测试数据，输出两个互质的正整数A和B（以A分之B表示小Hi能够追到小Z的几率）。
Sample Input
3 2
Sample Output
4 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<stdio.h>
#include <math.h>
long gcd(long, long);
int main()
{
    long m, n;
    scanf("%ld %ld", &m, &n);
    long temp;
    if(m > n) {
        temp = m;
        m = n;
        n = temp;
    }
    long same_sum = 0;
    long yinzi_m = 0;
    long yinzi_n = 0;
    for(long i = 1; i <= sqrt(m); i++)
    {
       if (m % i == 0 && n % i == 0) {
          same_sum++;
          yinzi_n++;
          yinzi_m++;
       }
       else if(m % i == 0) {
           yinzi_m++;
           if(n % (m / i) == 0) {
               same_sum++;
           }
       }
       else if (n % i == 0) {
           yinzi_n++;
       }
    }
    for (long i = sqrt(m) + 1; i <= sqrt(n); i++) {
        if(n % i == 0) {
            yinzi_n++;
        }
    }
    yinzi_m *= 2;
    yinzi_n *= 2;
    long max_yinzi;
    max_yinzi = gcd(same_sum, yinzi_n * yinzi_m);
    printf("%ld %ld", yinzi_n * yinzi_m / max_yinzi, same_sum / max_yinzi);
}
long gcd(long n, long m)
{
    long t;
    while(n) {
        t = m % n;
        m = n;
        n = t;
    }
    return m;
}